Tiuringo mašina

Animacija, iliustruojanti Tiuringo mašinos darbą

Tiuringo mašina – abstraktus kompiuterio vykdymo modelis, kurį 1936 metais sukūrė Alanas Tiuringas. Šis matematinis modelis leido formalizuoti algoritmo sąvoką.

Tiuringo mašina – tai automatas, vykdantis begalinę rūšiuotų instrukcijų seką, bei įsimenantis būseną. Skirtingų instrukcijų bei būsenų kiekiai – baigtiniai.

Aprašymas

Tiuringo mašiną sudaro:

• Juosta, padalinta į langelius, kuriuose gali būti vienas iš naudojamos abėcėlės simbolių. Abėcėlę sudaro tuščias simbolis ('0') ir vienas ar daugiau kitų simbolių. Į neužpildytus langelius žiūrima kaip užpildytus tuščiu simboliu.
• Galvutė, kuri skaito ir rašo į langelį, taip pat gali judėti į abi puses.
• Būsenų registras, saugantis automato būseną. Būsenų skaičius baigtinis, pradinė būsena visada apibrėžta.
• Veiksmų lentelė, nusakanti kokį simbolį rašyti, į kurią pusę per vieną langelį pajudėti ('K' į kairę, 'D' į dešinę), taip pat kokia bus nauja būsena priklausomai nuo esamos būsenos ir perskaitytos langelio reikšmės. Jei veiksmų lentelėje nėra aprašyto veiksmo dabartinei būsenai ir langelio reikšmei, mašina baigia darbą.

Formalus aprašymas

Vienos juostos Tiuringo mašina

Vienos juostos Tiuringo mašiną galima aprašyti kaip $M=(Q,\Gamma ,\Sigma ,s,b,F,\delta )$, kur

• $Q$ yra baigtinė būsenų aibė
• $\Gamma$ yra baigtinė juostos abėcėlės aibė
• $\Sigma$ baigtinė pradinė abėcėlė ($\Sigma \subseteq \Gamma$)
• $s\in Q$ yra pradinė būsena
• $b$ yra tuščias simbolis ($b\in \Gamma \setminus \Sigma$)
• $F\subseteq Q$ yra aibė galutinių arba priimamų būsenų
• $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{K,D\}$ yra dalinė funkcija, nusakanti perėjimą; K yra postūmis kairėn, D – dešinėn.

k - juostų Tiuringo mašina

Naudojant k juostų, Tiuringo mašiną taip pat galima aprašyti kaip $M=(Q,\Gamma ,\Sigma ,s,b,F,\delta )$, tik $\delta$ funkcija skirsis:

$\delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{K,D,S\})^{k}$; S – reiškia kad juosta paliekama toje pačioje pozicijoje

Rūšys

Jei kiekvienai simbolio ir būsenos porai yra daugiausiai viena reikšmė veiksmų lentelėje, Tiuringo mašina vadinama deterministine, priešingu atveju – nedeterministine.

Kiekviena Tiuringo mašina skaičiuoja dalinę suskaičiuojamą funkciją pagal paduotą pradinę simbolių seką, t. y. elgiasi kaip kompiuterio programa. Įrodyta, kad kiekvienos Tiuringo mašinos veiksmų lentelę galima užrašyti kaip simbolių seką. Taigi galima sukonstruoti tokią Tiuringo mašiną, kuri, gavusi kitos Tiuringo mašinos veiksmų lentelę ir pradinius duomenis kaip simbolių eilutę, suskaičiuos duotosios Tiuringo mašinos funkcijos rezultatą. Tokia mašina vadinama universaliąja Tiuringo mašina.

Nedeterministinę vienajuostę Tiuringo mašiną, kuri baigusi darbą sustoja ties pirma iš kairės tuščia ląstele, vadiname standartine Tiuringo mašina. Tokios mašinos abėcėle, būna aibė $A=\{0,1,b,q,2,\ldots ,9,\delta ,=,(,),K,D,N\}\cup \{,\}$

Tiuringo mašinos sustojimo problema

Ar egzistuoja algoritmas, kuris per baigtinį laiką nustatytų, ar bet kuri Tiuringo mašina su žinoma pradine juosta sustos?

Šis klausimas ekvivalentus klausimui Ar egzistuoja algoritmas, kuris per baigtinį laiką nustatytų, ar sustos universalioji Tiuringo mašina su žinoma pradine juosta?

Įrodoma, kad toks algoritmas neegzistuoja.

Tiuringo tezė

Tiuringo bei Churcho nepriklausomai suformuluota tezė, dar vadinama Churcho-Tiuringo teze ar Tiuringo teze:

Bet kuris procesas, kurį natūraliai būtų galima pavadinti efektyvia procedūra, gali būti realizuotas Tiuringo mašina.

Kai kada minima, jog ta ar kita kalba „atitinka Tiuringo standartą“. Tai reiškia, jog ja įmanoma užprogramuoti visas užduotis, kurias galėtų atlikti Tiuringo mašina. Pavyzdžiui, Asembleris, nors ir sunki kalba, Tiuringo standartą atitinka, tuo tarpu SQL – ne.